// 题目描述：
// 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
// 假设二叉树中至少有一个节点。
// 题目链接：https://leetcode.cn/problems/find-bottom-left-tree-value/
// 原文链接：https://blog.csdn.net/ITSOK_123/article/details/124966871

// 深度优先（O(N),O(N)）
class Solution {
public:
    // 其中num是需要记录返回的值，depth是当前访问的树结点的深度
    // curdepth是保存的返回值对应的节点的深度
    void getLeft(TreeNode* root, int &num,int depth,int &curdepth){
        if(root == nullptr) return;
        // 保存每一层的最左边元素
        if(root->left == nullptr && root->right == nullptr){
            // depth>curdepth就说明当前节点是本层最左边的
            if(depth > curdepth){
                curdepth = depth;
                num = root->val;
            }
        }
        getLeft(root->left,num,depth+1,curdepth);
        getLeft(root->right,num,depth+1,curdepth); 
    }
    int findBottomLeftValue(TreeNode* root) {
        int n = root->val;
        int dep = 0;
        if(!root->left && !root->right) return n;
        getLeft(root,n,1,dep);
        return n;
    }
};

// 广度优先（O(N),O(1)）
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        // 如果只有根节点，返回根结点的值
        if(!root ->left && !root->right) return root->val;
        // 层次遍历
        queue<TreeNode*> que;
        que.push(root);
        // 初始化返回值
        int res = 0;
        // 访问广度遍历队列
        while(!que.empty()){
            size_t size = que.size();
            TreeNode* node = nullptr;
            // 取每一层的最左边元素
            res = que.front()->val;
            // 按层处理元素
            while(size--){
                node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        // 返回结果
        return res;
    }
};